package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}9:41
 */
public class LeetCode62 {
    static class Node{
        private int val;
        private Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode62().lastRemaining(5, 3));
    }
    public int lastRemaining(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
    public int lastRemaining2(int n, int m) {
        if (n==0||m==0){
            return 0;
        }
        Node head = new Node(0);
        Node node = head;
        //初始化循环链表
        for (int i = 1; i < n; i++) {
            node.next = new Node(i);
            if (i + 1 == n) {
                node = node.next;
                node.next = head;
            } else {
                node = node.next;
            }
        }
        //双指针用来标记前一个和头
        Node pre = node;
        node = head;
        while (pre.next!=pre){
            for (int i = 0; i < m-1; i++){
                node = node.next;
                pre = pre.next;
            }
            pre.next = node.next;
            node = pre.next;
        }
        return pre.val;
    }
}
